#include <iostream>
#include <cstring>
using namespace std;
using ll=long long;
const int N=1e4+10;

int n,m;
ll g[110][110];
ll bg[110][110];
void back()
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			bg[i][j]=g[i][j];
}
int main()
{
	cin>>n>>m;
	memset(g,0x3f3f3f3f,sizeof(g));
	for(int i=0;i<m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);

		g[x][y]=z;
		g[y][x]=z;
	}
	
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(i==j)
					g[i][j]=0;
				g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
			}
		}
	}
	ll ret=2e9;
	for(int k=1;k<=n;k++)
	{
		for(int l=k+1;l<=n;l++)
		{
			back();
			bg[k][l]=bg[l][k]=0;
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					bg[i][j]=min(bg[i][j],bg[i][k]+bg[k][j]);
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					bg[i][j]=min(bg[i][j],bg[i][l]+bg[l][j]);	
			ll sum=0;
			for(int i=1;i<=n;i++)
			{
				for(int j=i+1;j<=n;j++)
				{
					sum+=bg[i][j];
				}
			}		
			ret=min(ret,sum);
		}
	}
	cout<<ret<<endl;
	return 0;
}
